/*
 * 1188. Minimum Absolute Difference in BST
 * Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
 * https://www.lintcode.com/problem/minimum-absolute-difference-in-bst/description
 * 
 * 样例
 * Input:
 * 1
 *  \
 *  3
 *  /
 *  2
 *  
 *  Output:
 *  1
 *  
 *  Explanation:
 *  The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
 * 
 * 2018.06.17 @jeyming
 */
package nimum_absolute_difference_in_bst_1188;

import java.util.Arrays;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

/**
 *Definition of TreeNode:
 */
class TreeNode {
	public int val;
	public TreeNode left, right;
	public TreeNode(int val) {
		this.val = val;
		this.left = this.right = null;
	}
}
public class Nimum_absolute_difference_in_bst_1188 {
    /**
     * @param root: the root
     * @return: the minimum absolute difference between values of any two nodes
     */
    public int getMinimumDifference(TreeNode root) {
        // Write your code here
    	int min = 0;
    	//List<Integer> list = new ArrayList<Integer>();
    	int[] nums = new int[1000];
    	int cnt = 0;
    	Queue<TreeNode> queue = new ArrayBlockingQueue<TreeNode>(1000);
    	TreeNode p = root;
    	queue.add(p);
    	while(queue.peek() != null) {
    		if(min < queue.peek().val)
    			min = queue.peek().val;
    		//list.add(queue.peek().val);
    		nums[cnt++] = queue.peek().val;
    		if(queue.peek().left != null) {
    			queue.add(queue.peek().left);
    		}
    		if(queue.peek().right != null) {
    			queue.add(queue.peek().right);
    		}
    		queue.remove();
    	}
//    	for(int i = 0; i < list.size() - 1; ++i) {
//    		for(int j = i + 1; j < list.size(); ++j) {
//    			if(Math.abs(list.get(i) - list.get(j)) < min) {
//    				min = Math.abs(list.get(i) - list.get(j));
//    			}
//    		}
//    	}
    	Arrays.sort(nums, 0, cnt);
    	for(int i = 0; i < cnt - 1; ++i) {
    		if(Math.abs(nums[i] - nums[i - 1]) > min) {
    			min = Math.abs(nums[i] - nums[i - 1]);
    		}
    	}
    	return min;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
